package com.zhz.leetcode;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * 189. 轮转数组
 * 给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
 * <p>
 * 示例 1:
 * 输入: nums = [1,2,3,4,5,6,7], k = 3
 * 输出: [5,6,7,1,2,3,4]
 * 解释:
 * 向右轮转 1 步: [7,1,2,3,4,5,6]
 * 向右轮转 2 步: [6,7,1,2,3,4,5]
 * 向右轮转 3 步: [5,6,7,1,2,3,4]
 * <p>
 * 示例 2:
 * 输入：nums = [-1,-100,3,99], k = 2
 * 输出：[3,99,-1,-100]
 * 解释:
 * 向右轮转 1 步: [99,-1,-100,3]
 * 向右轮转 2 步: [3,99,-1,-100]
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/rotate-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class RotateArray189 {

    public static void main(String[] args) {
        RotateArray189 m = new RotateArray189();
        //nums = [1,2,3,4,5,6,7], k = 3
        int[] nums = {1, 2, 3, 4, 5, 6, 7};
        int k = 3;
        m.rotate2(nums, k);
        System.out.println(Arrays.toString(nums));
    }

    /**
     * 思路：
     * 先取出后k位出来
     * 然后在将数组的数据全部往后移动k位
     * 最后将k位之后的数据插入到数组的前k位
     */
    public void rotate(int[] nums, int k) {
        int t = k % nums.length;
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = nums.length - t; i < nums.length; i++) {
            list.add(nums[i]);
        }
        for (int i = nums.length - t - 1; i >= 0; i--) {
            nums[i + t] = nums[i];
        }
        for (int i = 0; i < t; i++) {
            nums[i] = list.get(i);
        }
    }

    /**
     * 上面的优化思路：
     * 不使用ArrayList,而是使用一个数组,迭代将nums数组的数据放到buffer数组里面去 buffer[(i + k) % nums.length] = nums[i];
     * <p>
     * 这边是把k当作 k%nums.length 来看。也就是k不会大于nums.length
     *
     * <p>
     * 需要先理解下这个表示什么意思: (i+k)%nums.length
     * <p>
     * 如果i==0  buffer[k%nums.length] = nums[0] ， 即将nums[0]的数据，放到buffer的第k个位置去
     * 如果i==1 buffer[(k+1)%nums.length] = nums[1] ， 即将nums[1]的数据，放到buffer的第k+1个位置去
     * ...
     * 如果 i == length-k,此时,i+k = length ,于是(i+k)%nums.length = 0 ，此时会从buffer[0] = nums[i],从0开始放数据
     * 如果 i+k > nums.length 时， 此时(i+k)%nums.length  = i+k - nums.length  于是又会从buffer[0]开始放数据，
     * 以此类推...
     * <p>
     * 样式: [nums[k],nums[k+1],...,nums[length],..,nums[]]
     *
     * <p>
     * <p>
     * 然后将轮转后的数据插入到旧数据里面去
     */
    public void rotate1(int[] nums, int k) {
        int[] buffer = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            buffer[(i + k) % nums.length] = nums[i];
        }
        for (int i = 0; i < nums.length; i++) {
            nums[i] = buffer[i];
        }
    }


    /**
     * 思路，先将数组反转
     * 然后将数组的前k位反转
     * 接着将数组的后k位反转
     */
    public void rotate2(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }

    public void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int tmp = nums[end];
            nums[end] = nums[start];
            nums[start] = tmp;
            end--;
            start++;
        }
    }
}
